Question 4 ( 30 points ).

Consider the following collection of family trees where a line indicates the relationship between a father and his children.

A F

/ \ / | \

B C G H I

/ \ / \

D E J K

/ \

L M

Thus, for example,

· F is the father of G, H, and I

· F is the paternal grandfather of J and K

· F is the paternal great-grandfather of L and M

We say that two people have a "common paternal ancestor" if there is some person who is a paternal ancestor of both of them. For example, H is the common paternal ancestor of J and M, but J and D do not have a common paternal ancestor.

There are two special cases that follow from considering a person to be his own ancestor:

· A person is the common paternal ancestor of himself and all his children. For example, the common paternal ancestor of H and M is H.

· The common paternal ancestor of a person and himself is himself. For example, the common paternal ancestor of H and H is H.

Here is how you can compute whether person x and person y have a common paternal ancestor:

· Associate with each person a boolean "mark" that is assumed to be initially false.

· Start at person x and mark all of x's paternal ancestors (including x itself) true.

· Start at person y and consider y's paternal ancestors one-by-one, i.e., y, y'th father, etc. If you run into a marked person z, then z is a common paternal ancestor of x and y. If no such z is found, then x and y do not have a common paternal ancestor.

· Reset all the marks to be false to be ready for the next query.

Class Person, which is partially defined below, is used to implement a database of people and their family relationships. It is essentially the same class you used in Program 3. In this question, however, we only consider family relationships via fathers. Complete the implementation of instance method commonPaternalAncestor on the next page.

Solution

import java.io.*;

public class Person

{

/* other declarations and method definitions (such as those in program 3) are irrelevant to the present problem. */

private Person dad;

// Cross out one of the following two declarations.

boolean static mark;

boolean mark;

// Return true if this person and person b have a common paternal ancestor.

boolean commonPaternalAncestor( Person b )

{

// set the marks starting from b

Person p = b;

p.mark = true;

while( p.dad != null )

{

p = p.dad;

p.mark = true;

}

// set q to common ancestor ( if it exists ) or null otherwise

Person q = this;

while ( q != null && q.mark == false )

q = q.dad;

// clear the marks

b.mark = false;

while ( b.dad != null )

{

b = b.dad;

b.mark = false;

}

return q != null ;

}

}